# -*- coding: utf-8 -*-

"""剑指 Offer II 070. 排序数组中只出现一次的数字
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:
输入: nums =  [3,3,7,7,10,11,11]
输出: 10

提示:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5

进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？"""

class Solution:
    """重点条件，有序！只有一个元素落单，可从中截断，保留奇数长度的数组，最终停留在落单的元素"""
    def singleNonDuplicate(self, nums) -> int:
        head, tail = 0, len(nums)-1
        midd = (head+tail)//2
        while head < tail:
            midd = (head+tail)//2
            # print('head:%s, tail:%s, middle:%s' % ((head, nums[head]),(tail, nums[tail]),(midd, nums[midd])))
            if nums[midd] == nums[midd+1]:
                midd -= 1
            if (midd-head+1) % 2:
                tail = midd
            else:
                head = midd+1
        return nums[head]

if __name__ == '__main__':
    so = Solution()
    print(so.singleNonDuplicate([1,1,2,3,3,4,4,8,8]))
    print(so.singleNonDuplicate([3,3,7,7,10,11,11]))
